#include <bits/stdc++.h>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    void recursion(TreeNode* root,int count,vector<vector<int>>& res,vector<int>& record)
    {
        if(root->left==nullptr&&root->right==nullptr&&count==0)
        {
            res.push_back(record);
            return;
        }
        if(root->left)
        {
            record.push_back(root->left->val);
            recursion(root->left,count-root->left->val,res,record);
            record.pop_back();
        }
        if(root->right)
        {
            record.push_back(root->right->val);
            recursion(root->right,count-root->right->val,res,record);
            record.pop_back();
        }
    }
    vector<vector<int>> pathSum(TreeNode *root, int targetSum)
    {
        vector<vector<int>> res;
        if(root==nullptr)
        {
            return res;
        }
        vector<int> record;
        record.push_back(root->val);
        recursion(root,targetSum-root->val,res,record);
        return res;
    }
};

int main()
{
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->left = new TreeNode(5);
    root->right->right->right = new TreeNode(1);
    Solution sol;
    vector<vector<int>> res = sol.pathSum(root, 22);
    for (auto vec : res)
    {
        for (auto num : vec)
        {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}